
#ifndef etl_hash_h
#define etl_hash_h

#ifndef WIN32
  #pragma interface
#endif

#include "etl_base.h"
#include "etl_string.h"
#include "etl_list.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

namespace etl
{

/// etl_hash implements a chaining, automatically resizing associative array.
/// In addition, etl_hash is fast, providing O(1) amortized time lookups,
/// insertions and deletions for best case keys, and at worst O(N) lookups for
/// pathological cases. etl_hash is tightly integrated with the rest of the
/// k2 library, and requires etl_string's as keys.

template<class T>
class etl_hash : public etl_base<T>
{
  /// k2_bin_hash_list represents one chained element.
  class etl_hash_list
  {
    friend class  etl_hash;
  public:
    /// Constructor. Initializes minimal internal data structures to nil.
    etl_hash_list() : 
    next(NULL)
    {
    }
    /// Copy constructor. Sets this object to passed object.
    etl_hash_list(const etl_hash_list& obj)
    {
      copy(obj);
    }
    virtual ~etl_hash_list()
    {
    }
    /// Assigns this object to passed object.
    etl_hash_list& operator =(const etl_hash_list& obj)
    {
      return copy(obj);
    }

  private:
    /// Make our object match passed object.
    etl_hash_list& copy(const etl_hash_list& obj)
    {
      data = obj.data;
      key = obj.key;
      next = obj.next;
      return *this;
    }

    T             data;
    etl_string     key;
    etl_hash_list* next;
  };

public:
  enum etl_hash_enum
  {
    HASH_DJB2,
    HASH_PJW
  };

  typedef int (*hash_function)(long entry_count, const char* key, long* index);

  /// Constructor. Initializes table to nil state. 
  /// \param buckets Number of buckets initially in table. Optional.
  /// \param hash_type The kind of function to use when hashing a key.
  etl_hash(long buckets = 20, int hash_type = HASH_DJB2) :
    table( NULL ),
    hash_func((hash_type == HASH_DJB2) ? hash_djb2 : hash_pjw),
    entry_count(buckets),
    entrys_added(0)
  {
    table = (etl_hash_list **)
            malloc( sizeof(etl_hash_list*) * entry_count );
    memset(table, 0, sizeof(etl_hash_list *) * entry_count);
  }

  /// Copy Constructor. Initialize state to match obj.
  /// \param obj Object we are copying from.
  etl_hash(const etl_hash& obj) :
    table( NULL ),            
    hash_func( obj.hash_func ),
    entry_count( obj.entry_count ),
    entrys_added( obj.entrys_added )
  {
    table = (etl_hash_list **)malloc( sizeof(etl_hash_list*) * entry_count );
    memset(table, 0, sizeof(etl_hash_list *) * entry_count);

    copy(obj);
  }

  /// Destructor. Calls clear() on table.
  virtual ~etl_hash()
  {
    clear();

    if( table )
      free(table);
  }

  /// Add an element to this table given passed key.
  /// \param c_key const c string supplied to our hashing function.
  /// \param data The object we want associated with the key.
  int add( const char* c_key, T& data )
  {
    etl_string key = c_key;
    return add( key, data );
  }

  /// Add an element to this table given passed key.
  /// \param c_key The source data supplied to our hashing function.
  /// \param data The object we want associated with the key.
  int add(char* c_key, T& data)
  {
    etl_string  key = c_key;
    return add(key, data);
  }

  /// Add an element to this table given passed key.
  /// \param key The source data supplied to our hashing function.
  /// \param data The object we want associated with the key.
  int add(etl_string& key, T& data)
  {
    if( key.length() > 0 )
    {
      if( entrys_added >= (entry_count / 2) )
      {
        if( resize_table() != 0 )
          return -1;
      }

      long  new_index = 0;
      hash_func( entry_count, key.c_str(), &new_index );

      etl_hash_list* current = table[new_index];

      while( current )
      {
        if( current->key == key )
          return -1;
        current = current->next;
      }

      /// If we're here, we know their are no more in the list...

      etl_hash_list*new_node = new etl_hash_list;

      if( new_node )
      {
        new_node->data = data;
        new_node->key = key;

        new_node->next = (table[new_index]) ? table[new_index] : NULL;

        // prepend...
        table[new_index] = new_node;

        key_list.prepend(key);

        entrys_added++;

        return 0;
      }
    }
    return -1;
  }

  /// Find the object associated with this key.
  /// \param key The key to lookup in our table.
  T* find(const char* c_key)
  {
    etl_string  key = c_key;
    return find(key);
  }

  /// Find the object associated with this key.
  /// \param key The key to lookup in our table.
  T* find(const etl_string& key)
  {
    long  new_index = 0;
    etl_hash_list*current = NULL;
    if( key.length() > 0 )
    {
      hash_func(entry_count, key.c_str(), &new_index);

      current = table[new_index];

      while( current && (current->key != key) )
        current = current->next;      
    }

    return(current) ? &current->data : 0;
  }

  /// Find the object associated with the key passed in the brackets.
  /// \param c_key The key to lookup in our table.
  T* operator[] ( char* c_key )
  {
    etl_string key = c_key;
    return(*this)[key];
  }

  /// Find the object associated with the key passed in the brackets.
  /// \param key The key to lookup in our table.
  T* operator[] ( etl_string& key )
  {
    return find( key );
  }

  /// Remove an object from our table
  /// \param c_key The key to lookup in our table.
  int remove(char* c_key)
  {
    etl_string  key = c_key;
    return remove(key);
  }

  /// Remove an object from our table.
  /// \param key The key to lookup in our table.
  int remove(etl_string& key)
  {
    long  new_index = 0;
    if( key.length() > 0 )
    {
      hash_func(entry_count, key.c_str(), &new_index);

      etl_hash_list*last = NULL;
      etl_hash_list*current = table[new_index];

      while( current && (current->key != key) )
      {
        last = current;
        current = current->next;
      }

      if( current && (current->key == key) )
      {
        if( last )
          last->next = current->next;
        else
          table[new_index] = current->next;      

        delete(current);

        return key_list.remove_all( key );
      }
    }

    return -1;
  }

  /// Empty this container.
  virtual int clear()
  {
    for( long i = 0; i < entry_count; i++ )
    {
      while( etl_hash_list * current = table[i] )
      {
        table[i] = table[i]->next;
        delete current;
      }
    }

    key_list.clear();

    if( table )
      free(table);

    table = NULL;
    entry_count = 20;
    entrys_added = 0;

    table = (etl_hash_list**)
            malloc(sizeof(etl_hash_list *) * entry_count);
    memset(table, 0, sizeof(etl_hash_list *) * entry_count);

    return 0;
  }

  /// Reset our internal iterator to the head, or beginning of the set.
  virtual int iter_begin()
  {
    return key_list.iter_begin();
  }

  /// Reset our internal iterator to the end of the set.
  virtual int iter_end()
  {
    return key_list.iter_end();
  }

  /// Move our iterator to the next item contained in this object.
  virtual int iter_next()
  {
    return key_list.iter_next();
  }

  /// Move our iterator to the previous item contained in this object.
  virtual int iter_prev()
  {
    return key_list.iter_prev();
  }

  /// Return a pointer to the object currently pointed to by our internal
  /// iterator.
  virtual T* iter_data()
  {
    return find(*key_list.iter_data());
  }

  /// Returns whether or not the internal iterator is pointing at something
  /// valid, or has walked off the end of the set.
  virtual bool iter_valid()
  {
    return key_list.iter_valid();
  }

  /// Allow assignment of one hash table to another.
  /// \param obj The object we copy FROM.
  etl_hash& operator =(const etl_hash& obj)
  {
    return copy(obj);
  }

  /// Our key_list is public!
  ///
  etl_list<etl_string>  key_list;

private:

  /// Internal function. Copy's the passed hash table into our hash table.
  /// \param obj The object we copy FROM.
  etl_hash& copy(const etl_hash& obj)
  {
    etl_hash* non_const_obj = const_cast<etl_hash*>(&obj);

    clear();      

    non_const_obj->key_list.iter_begin();

    while( non_const_obj->key_list.iter_valid() )
    {
      etl_string  key = *non_const_obj->key_list.iter_data();
      add(key, *non_const_obj->find(key));
      non_const_obj->key_list.iter_next();
    }

    return *this;
  }

  /// Creates a new table twice the size of the old table, and re-inserts all
  /// of the data into the new table.
  int resize_table()
  {
    long new_entry_count = entry_count * 2;
    etl_hash_list** new_table = (etl_hash_list**)
                                   malloc(sizeof(etl_hash_list*) * new_entry_count);
    memset(new_table, 0, sizeof(etl_hash_list *) * new_entry_count);

    if( new_table )
    {
      for( long i = 0; i < entry_count; i++ )
      {
        while( etl_hash_list* current = table[i] )
        {
          etl_hash_list* new_node = new etl_hash_list;
          if( new_node )
          {
            new_node->data = current->data;
            new_node->key = current->key;

            long new_index = 0;
            hash_func(new_entry_count, current->key.c_str(), &new_index);

            new_node->next = (new_table[new_index])
                             ? new_table[new_index]
                             : NULL;

            // prepend...
            new_table[new_index] = new_node;
          }
          else
            return -1;

          etl_hash_list* tmp = table[i];
          table[i] = table[i]->next;
          delete tmp;
        }
      }

      free(table);

      entry_count = new_entry_count;
      table = new_table;

      return 0;
    }
    return -1;
  }

  /// Peter J. Weinberger's hash function.
  static int hash_pjw(long entry_count, const char* key, long* index)
  {
    unsigned g = 0, i, h;
    for( i = 0, h = entry_count; key[i] != '\0'; i++ )
    {
      h = (h << 4) + key[i];
      if( (g = h && 0xf0000000) )
      {
        h ^= g >> 24;
        h ^= g;
      }
    }
    *index = h % entry_count;
    return 0;
  }

  /// An algorithm produced by Daniel J. Bernstein.
  static int hash_djb2(long entry_count, const char* key, long* index)
  {
    unsigned long hash = 5381;
    int c = 0;
    while( (c = *key++) )
      hash = ((hash << 5) + hash) + c;
    *index = hash % entry_count;
    return 0;
  }

  etl_hash_list** table;
  hash_function hash_func;  
  long entry_count;
  long entrys_added;
};

class k2_bin_hash_key
{
public:
  unsigned long get_size()
  {
    return KeySize; 
  }
  void set_size(unsigned long sizeOfKey)
  {
    KeySize = sizeOfKey;
  }
  void* get_key_data()
  {
    return KeyData;
  }
  void set_key_data(void* data, unsigned long sizeOfKey)
  {
    KeySize = sizeOfKey;
    if( KeyData != NULL )
      free( KeyData );
    KeyData = malloc(KeySize);
    memcpy(this->KeyData,data,KeySize);
  }
  bool operator==(const k2_bin_hash_key& obj)
  {
    if( this->KeySize == obj.KeySize )
      if( memcmp(this->KeyData,obj.KeyData,KeySize) == 0 )
        return true;
    return false;
  }
  bool operator!=(const k2_bin_hash_key& obj)
  {
    return !(*this == obj);
  }
private:
  void* KeyData;
  unsigned long KeySize;
  k2_bin_hash_key& copy(const k2_bin_hash_key& obj)
  {
    this->KeySize = obj.KeySize;
    if( this->KeyData != NULL )
      free( KeyData );
    KeyData = malloc(KeySize);
    memcpy(this->KeyData,obj.KeyData,KeySize);
    return *this;
  }
public:
  k2_bin_hash_key():KeyData(NULL),KeySize(0)
  {
  }
  k2_bin_hash_key(void* keyData, unsigned long keySize):KeyData(NULL),KeySize(0)
  {
    KeySize = keySize;
    KeyData = malloc(KeySize);
    memcpy(this->KeyData,keyData,KeySize);
  }
  virtual ~k2_bin_hash_key()
  {
    if( this->KeyData != NULL )
      free( KeyData );
  }
  k2_bin_hash_key(const k2_bin_hash_key& obj):KeyData(NULL),KeySize(0)
  {
    copy(obj);
  }
  k2_bin_hash_key& operator=(const k2_bin_hash_key& obj)
  {
    return copy(obj);
  }
};

template<class T>
class k2_bin_hash : public etl_base<T>
{
  /// k2_bin_hash_list represents one chained element.
  class k2_bin_hash_list
  {
    friend class  k2_bin_hash;
  public:
    /// Constructor. Initializes minimal internal data structures to nil.
    k2_bin_hash_list() : 
    next(NULL)
    {
    }
    /// Copy constructor. Sets this object to passed object.
    k2_bin_hash_list(const k2_bin_hash_list& obj)
    {
      copy(obj);
    }
    virtual ~k2_bin_hash_list()
    {
    }
    /// Assigns this object to passed object.
    k2_bin_hash_list& operator =(const k2_bin_hash_list& obj)
    {
      return copy(obj);
    }
  private:
    /// Make our object match passed object.
    k2_bin_hash_list& copy(const k2_bin_hash_list& obj)
    {
      data = obj.data;
      key = obj.key;
      next = obj.next;
      return *this;
    }
    T data;
    k2_bin_hash_key key;
    k2_bin_hash_list* next;
  };

public:
  enum etl_hash_enum
  {
    HASH_DJB2,
    HASH_PJW
  };

  typedef int (*hash_function)(long entry_count, k2_bin_hash_key& key, long* index);

  /// Constructor. Initializes table to nil state. 
  /// \param buckets Number of buckets initially in table. Optional.
  /// \param hash_type The kind of function to use when hashing a key.
  k2_bin_hash(long buckets = 20, int hash_type = HASH_DJB2) : hash_func((hash_type == HASH_DJB2) ? hash_djb2 : hash_pjw),entry_count(buckets), entrys_added(0)
  {
    table = (k2_bin_hash_list **)malloc( sizeof(k2_bin_hash_list*) * entry_count );
    memset(table, 0, sizeof(k2_bin_hash_list *) * entry_count);
  }

  /// Copy Constructor. Initialize state to match obj.
  /// \param obj Object we are copying from.
  k2_bin_hash(const k2_bin_hash& obj)
  {
    copy(obj);
  }

  /// Destructor. Calls clear() on table.
  virtual ~k2_bin_hash()
  {
    clear();
    if( table )
      free(table);
    table = NULL;
  }

  int add(void* key, unsigned long keySize, T& data)
  {
    k2_bin_hash_key k(key,keySize);
    return add(k,data);
  }

  /**
   * Add an element to this table given passed key.
   * 
   * @param key
   * @param data
   * 
   * @return int
   */
  int add(k2_bin_hash_key& key, T& data)
  {
    if( key.get_size() > 0 )
    {
      if( entrys_added >= (entry_count / 2) )
      {
        if( resize_table() != 0 )
          return -1;
      }
      long  new_index = 0;
      hash_func(entry_count, key, &new_index);
      k2_bin_hash_list* current = table[new_index];
      while( current )
      {
        if( current->key == key )
          return -1;
        current = current->next;
      }
      /// If we're here, we know their are no more in the list...
      k2_bin_hash_list* new_node = new k2_bin_hash_list;
      if( new_node )
      {
        new_node->data = data;
        new_node->key = key;
        new_node->next = (table[new_index]) ? table[new_index] : NULL;
        // prepend...
        table[new_index] = new_node;
        key_list.prepend(key);
        entrys_added++;
        return 0;
      }
    }
    return -1;
  }

  T* find(void* key, unsigned long keySize)
  {
    k2_bin_hash_key k(key,keySize);
    return find(k);
  }
  /// Find the object associated with this key.
  /// \param key The key to lookup in our table.
  T* find(k2_bin_hash_key& key)
  {
    long new_index = 0;
    k2_bin_hash_list* current = NULL;
    if( key.get_size() > 0 )
    {
      hash_func(entry_count, key, &new_index);
      current = table[new_index];
      while( current && (current->key != key) )
        current = current->next;      
    }
    return(current) ? &current->data : 0;
  }

  /// Find the object associated with the key passed in the brackets.
  /// \param key The key to lookup in our table.
  T* operator[] ( k2_bin_hash_key key )
  {
    return find( key );
  }

  int remove(void* key, unsigned long keySize)
  {
    return remove(k2_bin_hash_key(key,keySize));
  }
  /// Remove an object from our table.
  /// \param key The key to lookup in our table.
  int remove(k2_bin_hash_key& key)
  {
    long  new_index = 0;
    if( key.get_size() > 0 )
    {
      hash_func(entry_count, key, &new_index);
      k2_bin_hash_list*last = NULL;
      k2_bin_hash_list*current = table[new_index];
      while( current && (current->key != key) )
      {
        last = current;
        current = current->next;
      }
      if( current && (current->key == key) )
      {
        if( last )
          last->next = current->next;
        else
          table[new_index] = current->next;      
        delete(current);
        return key_list.remove_all( key );
      }
    }
    return -1;
  }

  /// Empty this container.
  virtual int clear()
  {
    for( long i = 0; i < entry_count; i++ )
      while( k2_bin_hash_list * current = table[i] )
      {
        table[i] = table[i]->next;
        delete current;
      }
    key_list.clear();
    if( table )
      free(table);
    table = NULL;
    entry_count = 20;
    entrys_added = 0;
    table = (k2_bin_hash_list**)malloc(sizeof(k2_bin_hash_list*)*entry_count);
    memset(table, 0, sizeof(k2_bin_hash_list*)*entry_count);
    return 0;
  }

  /// Reset our internal iterator to the head, or beginning of the set.
  virtual int iter_begin()
  {
    return key_list.iter_begin();
  }

  /// Reset our internal iterator to the end of the set.
  virtual int iter_end()
  {
    return key_list.iter_end();
  }

  /// Move our iterator to the next item contained in this object.
  virtual int iter_next()
  {
    return key_list.iter_next();
  }

  /// Move our iterator to the previous item contained in this object.
  virtual int iter_prev()
  {
    return key_list.iter_prev();
  }

  /// Return a pointer to the object currently pointed to by our internal
  /// iterator.
  virtual T* iter_data()
  {
    return find(*key_list.iter_data());
  }

  /// Returns whether or not the internal iterator is pointing at something
  /// valid, or has walked off the end of the set.
  virtual bool iter_valid()
  {
    return key_list.iter_valid();
  }

  /// Allow assignment of one hash table to another.
  /// \param obj The object we copy FROM.
  k2_bin_hash& operator =(const k2_bin_hash& obj)
  {
    return copy(obj);
  }

  /// Our key_list is public!
  ///
  etl_list<k2_bin_hash_key>  key_list;

private:

  /// Internal function. Copy's the passed hash table into our hash table.
  /// \param obj The object we copy FROM.
  k2_bin_hash& copy(const k2_bin_hash& obj)
  {
    k2_bin_hash* non_const_obj = const_cast<k2_bin_hash*>(&obj);
    clear();      
    non_const_obj->key_list.iter_begin();
    while( non_const_obj->key_list.iter_valid() )
    {
      k2_bin_hash_key key = *non_const_obj->key_list.iter_data();
      add(key, *non_const_obj->find(key));
      non_const_obj->key_list.iter_next();
    }
    return *this;
  }

  /// Creates a new table twice the size of the old table, and re-inserts all
  /// of the data into the new table.
  int resize_table()
  {
    long new_entry_count = entry_count * 2;
    k2_bin_hash_list** new_table = (k2_bin_hash_list**)malloc(sizeof(k2_bin_hash_list*) * new_entry_count);
    memset(new_table, 0, sizeof(k2_bin_hash_list *) * new_entry_count);
    if( new_table )
    {
      for( long i = 0; i < entry_count; i++ )
      {
        while( k2_bin_hash_list* current = table[i] )
        {
          k2_bin_hash_list* new_node = new k2_bin_hash_list;
          if( new_node )
          {
            new_node->data = current->data;
            new_node->key = current->key;
            long new_index = 0;
            hash_func(new_entry_count, current->key, &new_index);
            new_node->next = (new_table[new_index]) ? new_table[new_index] : NULL;
            // prepend...
            new_table[new_index] = new_node;
          }
          else
            return -1;
          k2_bin_hash_list* tmp = table[i];
          table[i] = table[i]->next;
          delete tmp;
        }
      }
      free(table);
      entry_count = new_entry_count;
      table = new_table;
      return 0;
    }
    return -1;
  }

  /// Peter J. Weinberger's hash function.
  static int hash_pjw(long entry_count, k2_bin_hash_key& key, long* index)
  {
    unsigned g = 0, i, h;
    unsigned char* c = (unsigned char*)key.get_key_data();
    unsigned long size = key.get_size();
    for( i = 0, h = entry_count; i < size; i++ )
    {
      h = (h << 4) + c[i];
      if( (g = h && 0xf0000000) )
      {
        h ^= g >> 24;
        h ^= g;
      }
    }
    *index = h % entry_count;
    return 0;
  }

  /// An algorithm produced by Daniel J. Bernstein.
  static int hash_djb2(long entry_count, k2_bin_hash_key& key, long* index)
  {
    unsigned long hash = 5381;
    unsigned char* k = (unsigned char*)key.get_key_data();
    unsigned long size = key.get_size();
    for( unsigned long s = 0; s < size; ++s )
      hash = ((hash << 5) + hash) + k[s];
    *index = hash % entry_count;
    return 0;
  }

  k2_bin_hash_list** table;
  hash_function hash_func;  
  long entry_count;
  long entrys_added;
};

/// This class is a specialization of the generic etl_hash. It's main purpose
/// is to add serialization capabilities to a specialization of etl_hash, a
/// hash of etl_strings.
/// Hences, etl_string_hash is a hash table that can only store strings, but
/// can be serialized and de-serialized at will.
class etl_string_hash : public etl_hash<etl_string>
{
public:
  /// This function converts this object into it's serialized representation.
  etl_string to_string()
  {
    etl_string serializedHash;
    key_list.iter_begin();
    while( key_list.iter_valid() )
    {
      etl_string key = *key_list.iter_data();
      etl_string value = *find( key );
      etl_string encodedKey = 
      etl_string::to_base64( (unsigned char*)key.c_str(), key.length()+1 );
      etl_string encodedValue = 
      etl_string::to_base64( (unsigned char*)value.c_str(), value.length()+1 );
      serializedHash += encodedKey;
      serializedHash += "%";
      serializedHash += encodedValue;
      serializedHash += "|";
      key_list.iter_next();
    }
    return serializedHash;
  }

  /// This static function creates a etl_string_hash given a string
  /// representation previousley returned by etl_string_hash.to_string().
  static int from_string( etl_string_hash& obj, etl_string string_rep )
  {
    etl_list<etl_string> nvPairs;
    string_rep.split( "|", nvPairs );
    nvPairs.iter_begin();
    if( nvPairs.iter_valid() )
    {
      while( nvPairs.iter_valid() )
      {
        etl_string nvPair = *nvPairs.iter_data();
        etl_list<etl_string> pieces;
        nvPair.split( "%", pieces );
        pieces.iter_begin();
        if( pieces.iter_valid() )
        {
          etl_string key = *pieces.iter_data();
          pieces.iter_next();
          if( pieces.iter_valid() )
          {
            etl_string val = *pieces.iter_data();

            // This function uses a very old school (from the C 
            // programing times of olde) mechanism of exception
            // handling. I like it because unlike with C++ 
            // exceptions I KNOW where the error handling code is
            // (the catch block). Because it relys on goto, by
            // definition your "catch block" must be within your
            // current stack frame.

            unsigned char* decodedKey = NULL;
            unsigned char* decodedVal = NULL;
            etl_string k;
            etl_string v;

            key.from_base64( &decodedKey );
            if( !decodedKey )
              goto ESC_1;

            val.from_base64( &decodedVal );
            if( !decodedVal )
              goto ESC_2;

            k = (char*)decodedKey;
            v = (char*)decodedVal;

            obj.add( k, v );

            free( decodedVal );
            free( decodedKey );

            // everything worked, so continue to the next nv pair.
            nvPairs.iter_next();
            continue;

            ESC_2:
            free( decodedKey );
            ESC_1:
            // first alloc failed, so nothing to free

            return -1;         

          }
          else return -1;
        }
        else return -1;
      }
      return 0;
    }
    return -1;
  }
};

}

#endif

